{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coin Change"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: coinChange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #零钱兑换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>coins</code> ，表示不同面额的硬币；以及一个整数 <code>amount</code> ，表示总金额。</p>\n",
    "\n",
    "<p>计算并返回可以凑成总金额所需的 <strong>最少的硬币个数</strong> 。如果没有任何一种硬币组合能组成总金额，返回&nbsp;<code>-1</code> 。</p>\n",
    "\n",
    "<p>你可以认为每种硬币的数量是无限的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = <code>[1, 2, 5]</code>, amount = <code>11</code>\n",
    "<strong>输出：</strong><code>3</code> \n",
    "<strong>解释：</strong>11 = 5 + 5 + 1</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = <code>[2]</code>, amount = <code>3</code>\n",
    "<strong>输出：</strong>-1</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1], amount = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= coins.length &lt;= 12</code></li>\n",
    "\t<li><code>1 &lt;= coins[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>0 &lt;= amount &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coin-change](https://leetcode.cn/problems/coin-change/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coin-change](https://leetcode.cn/problems/coin-change/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5]\\n11', '[2]\\n3', '[1]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def opt(coins, amount, cache):\n",
    "    if amount in cache:\n",
    "        return cache[amount]\n",
    "    if amount == 0:\n",
    "        return 0\n",
    "    minCoins = float('inf')\n",
    "    for coin in coins:\n",
    "        if coin <= amount:\n",
    "            minCoins = min(minCoins, opt(coins, amount - coin, cache) + 1)\n",
    "    cache[amount] = minCoins\n",
    "    \n",
    "    return minCoins\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        res = opt(coins, amount, {})\n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "        if coins == []:\n",
    "            return -1\n",
    "        n = len(coins)\n",
    "        memo = [-1 for j in range(amount + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, amount + 1):\n",
    "                if j < coins[i]:\n",
    "                    if i == 0:\n",
    "                        memo[j] = -1\n",
    "                elif j == coins[i]:\n",
    "                    memo[j] = 1\n",
    "                else:\n",
    "                    if i == 0:\n",
    "                        if memo[j - coins[i]] > 0:\n",
    "                            memo[j] = memo[j - coins[i]] + 1\n",
    "                        else:\n",
    "                            memo[j] = -1\n",
    "                    else:\n",
    "                        if memo[j - coins[i]] > 0 and memo[j] > 0:\n",
    "                            memo[j] = min(memo[j], 1 + memo[j - coins[i]])\n",
    "                        elif memo[j - coins[i]] > 0:\n",
    "                            memo[j] = 1 + memo[j - coins[i]]\n",
    "\n",
    "        # print(memo)\n",
    "        return memo[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        dp = [1e9 for _ in range(amount+1)]\n",
    "        dp[0] = 0\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j] = min(dp[j-coins[i]]+1,dp[j])\n",
    "        \n",
    "        if dp[amount] == 1e9:   \n",
    "            return -1\n",
    "        else:\n",
    "            return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        dp=[sys.maxsize]*(amount+1)\n",
    "        dp[0]=0\n",
    "        for coin in coins:\n",
    "            for j in range(coin,amount+1):\n",
    "                if dp[j-coin]!=sys.maxsize:\n",
    "                    dp[j]=min(dp[j],dp[j-coin]+1)        \n",
    "        return dp[-1] if dp[-1]!=sys.maxsize else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        n = len(coins)\n",
    "        dp = [[amount + 1 for j in range(amount + 1)] for i in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, amount + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j >= coins[i - 1]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1)\n",
    "        return dp[-1][-1] if dp[-1][-1] <= amount else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 暴力解法\n",
    "    # def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "    #     if amount == 0:\n",
    "    #         return 0\n",
    "    #     elif amount < 0:\n",
    "    #         return -1\n",
    "    #     else:\n",
    "    #         res = float('inf')\n",
    "    #         for i in range(len(coins)):\n",
    "    #             subnum = self.coinChange(coins, amount - coins[i])\n",
    "    #             if subnum == -1:\n",
    "    #                 continue\n",
    "    #             res = min(res, subnum + 1)\n",
    "    #         if res != float('inf'):\n",
    "    #             return res\n",
    "    #         else:\n",
    "    #             return -1\n",
    "    ### 带备忘录了\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo = [-666]*(amount + 1)\n",
    "        def dp(coins, amount):\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "            elif amount < 0:\n",
    "                return -1\n",
    "            if memo[amount] != -666:\n",
    "                return memo[amount]\n",
    "            res = float('inf')\n",
    "            for i in range(len(coins)):\n",
    "                subnum = dp(coins, amount - coins[i])\n",
    "                if subnum == -1:\n",
    "                    continue\n",
    "                res = min(res, subnum + 1)\n",
    "            if res != float('inf'):\n",
    "                memo[amount] = res\n",
    "                return res\n",
    "            else:\n",
    "                memo[amount] = -1\n",
    "                return -1\n",
    "        return dp(coins, amount)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(target):\n",
    "            if target == 0:\n",
    "                return 0\n",
    "\n",
    "            res = 1 << 31 - 1\n",
    "\n",
    "            for c in coins:\n",
    "                if target - c >= 0:\n",
    "                    res = min(dfs(target - c) + 1, res)\n",
    "\n",
    "            return res\n",
    "\n",
    "        res = dfs(amount)\n",
    "        if res == 1 << 31 - 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        import functools \n",
    "\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(_amount):\n",
    "\n",
    "            if _amount == 0:\n",
    "                return 0\n",
    "\n",
    "            if _amount < 0:\n",
    "                return -1 \n",
    "            \n",
    "            _min = 999999\n",
    "            for coin in coins:\n",
    "                tmp = dp(_amount - coin)\n",
    "                if tmp != -1:\n",
    "                    _min = min(tmp + 1, _min)\n",
    "\n",
    "            if _min == 999999:\n",
    "                return -1\n",
    "\n",
    "            return _min\n",
    "\n",
    "        return dp(amount)\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount == 0:return 0\n",
    "        memo = {}\n",
    "        def dp(n):\n",
    "            if n in memo: return memo[n]\n",
    "            if n == 0:return 0\n",
    "            if n < 0: return -1\n",
    "            res = float('inf')\n",
    "            for coin in coins:\n",
    "                if dp(n-coin) == -1:continue\n",
    "                res = min(res,dp(n-coin)+1)\n",
    "            memo[n] = res if res != float('inf') else -1\n",
    "            return memo[n]\n",
    "        return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        calculated = {}\n",
    "\n",
    "        def dp(amount):\n",
    "\n",
    "            if amount in calculated: return calculated[amount]\n",
    "\n",
    "            if amount == 0: return 0\n",
    "            if amount < 0: return -1\n",
    "            \n",
    "\n",
    "            res = float(\"inf\")\n",
    "\n",
    "            for coin in coins:\n",
    "                \n",
    "                subproblem = dp(amount - coin)\n",
    "\n",
    "                if subproblem == -1:\n",
    "                    continue\n",
    "                \n",
    "                res = min(res, 1 + subproblem)\n",
    "                # wrong place to record the res for amount\n",
    "                # calculated[amount] = res\n",
    "            \n",
    "            # we are targeting for amount, so we need to record the res after all coins visited\n",
    "            calculated[amount] = res\n",
    "\n",
    "            # the reason to check res has been updated is to avoid\n",
    "            # corner case such as coins=[2], amount=3,\n",
    "            # the for-loop is executed once, and float(\"inf\") will be returned\n",
    "            # so we need to forced to be -1 if no res has been updated\n",
    "            return calculated[amount] if res != float(\"inf\") else -1\n",
    "\n",
    "        return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        @functools.lru_cache(amount)\n",
    "        def dp(amount):\n",
    "            if amount < 0: return -1\n",
    "            if not amount: return 0\n",
    "            res = float('inf')\n",
    "            for coin in reversed(coins):\n",
    "                t = dp(amount-coin)\n",
    "                if t > -1 and t + 1 < res:\n",
    "                    res = t + 1\n",
    "            return res if res < float('inf') else -1\n",
    "        return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "        @functools.lru_cache(amount)\n",
    "        def dp(amount):\n",
    "            if amount < 0: return -1\n",
    "            if not amount: return 0\n",
    "            res = float('inf')\n",
    "            for coin in reversed(coins):\n",
    "                t = dp(amount-coin)\n",
    "                if t > -1 and t + 1 < res:\n",
    "                    res = t + 1\n",
    "            return res if res < float('inf') else -1\n",
    "        return dp(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import inf\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res_dict = {}\n",
    "\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        def dp(amount):\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "            if amount < 0:\n",
    "                return -1\n",
    "            if amount in self.res_dict:\n",
    "                return self.res_dict[amount]\n",
    "            res = float(inf)\n",
    "            for c in coins:\n",
    "                sub_res = dp(amount - c)\n",
    "                if sub_res == -1:\n",
    "                    continue\n",
    "                res = min(res, sub_res+1)\n",
    "            self.res_dict[amount] = res\n",
    "            return res if res < float(inf) else -1\n",
    "\n",
    "        return dp(amount)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        dp = {}\n",
    "        def f(n):\n",
    "            if n < 0:\n",
    "                return False,0\n",
    "\n",
    "            if n in dp:\n",
    "                return dp[n]\n",
    "\n",
    "            if n == 0:\n",
    "                return True,0\n",
    "\n",
    "            min_num = None\n",
    "            for coin in coins:\n",
    "                flag,num =  f(n - coin)\n",
    "                if flag:\n",
    "                    if min_num is None:\n",
    "                        min_num = num + 1\n",
    "                    elif min_num > num + 1:\n",
    "                        min_num = num + 1\n",
    "  \n",
    "            if min_num is None:\n",
    "                res = (False,-1)\n",
    "            else:\n",
    "                res = (True,min_num)\n",
    "\n",
    "            dp[n] = res\n",
    "            return res\n",
    "        \n",
    "        flag,num = f(amount)\n",
    "        return num\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, a: List[int], amount: int) -> int:\n",
    "        MAX = 999999\n",
    "        a.sort()\n",
    "        b = [a[0]]\n",
    "        for x in a[1:]:\n",
    "            b.append(gcd(x, b[-1]))\n",
    "        @cache\n",
    "        def f(x, k):\n",
    "            if x % a[k] ==0:\n",
    "                return x//a[k]\n",
    "            if x % b[k] !=0:\n",
    "                return MAX\n",
    "            ans = MAX\n",
    "            for m in range(x//a[k], -1, -1):\n",
    "                s = x - m *a[k]\n",
    "                if s//a[k-1]+m >ans: break\n",
    "                ans = min(ans, f(s, k-1) + m)\n",
    "            return ans\n",
    "        ans = f(amount, len(a)-1) \n",
    "        return -1 if ans == MAX else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        numbers = [0]\n",
    "        num_index = {0: 0}\n",
    "        def find(numbers, layer=1):\n",
    "            if min(numbers) > amount:\n",
    "                return\n",
    "            _numbers = numbers[:]\n",
    "            numbers = []\n",
    "            for num in _numbers:\n",
    "                for coin in coins:\n",
    "                    new_num = num + coin\n",
    "                    if not num_index.get(new_num):\n",
    "                        num_index[new_num] = layer\n",
    "                        numbers.append(new_num)\n",
    "            find(numbers, layer+1)\n",
    "        find(numbers)\n",
    "        return num_index.get(amount, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution(object):\n",
    "    def coinChange(self, coins, amount):\n",
    "        \"\"\"\n",
    "        :type coins: List[int]\n",
    "        :type amount: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        coins.sort()\n",
    "        self.coins = coins\n",
    "        @lru_cache(None)\n",
    "        def process(index, rest):\n",
    "            if rest < 0:\n",
    "                return -1\n",
    "            if rest == 0:\n",
    "                return 0\n",
    "            if index == len(self.coins):\n",
    "                return -1\n",
    "            minv = 10000\n",
    "            for i in range(index, len(self.coins)):\n",
    "                if self.coins[i] > rest:\n",
    "                    break\n",
    "                p = process(index, rest - self.coins[i])\n",
    "                if p != -1:\n",
    "                    minv = min(minv, p)\n",
    "            if minv == 10000:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1 + minv\n",
    "        return process(0, amount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index,cur_sum):\n",
    "            if cur_sum==amount:\n",
    "                return 0\n",
    "            if cur_sum>amount:\n",
    "                return float(\"inf\")\n",
    "            res=float(\"inf\")\n",
    "            for i in range(index,len(coins)):\n",
    "                # #不选i，就把index+1\n",
    "                # a1=dfs(index+1,cur_sum)\n",
    "                # #选i\n",
    "                a2=dfs(index,cur_sum+coins[i])+1\n",
    "                res=min(res,a2)\n",
    "                # cur_ans=min(a1,a2)\n",
    "                # res=min(res,cur_ans)\n",
    "            return res \n",
    "        res=dfs(0,0)\n",
    "        if res==float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def coinChange(self, coins, amount):\n",
    "        count = [0] * 100000 \n",
    "        def dp(coins, rem) -> int:\n",
    "            if rem < 0: return -1\n",
    "            if rem == 0: return 0\n",
    "            if count[rem - 1]:\n",
    "                return count[rem - 1]\n",
    "            mini = int(1e9)\n",
    "            for coin in self.coins:\n",
    "                res = dp(coins, rem - coin)\n",
    "                if res >= 0 and res < mini:\n",
    "                    mini = res + 1\n",
    "            count[rem - 1] = mini if mini < int(1e9) else -1    \n",
    "            return count[rem - 1]\n",
    "\n",
    "        self.coins = coins\n",
    "        if amount < 1: return 0\n",
    "        return dp(coins, amount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(i, target):\n",
    "            name = '{}_{}'.format(i, target)\n",
    "            if name in memo:\n",
    "                return memo[name]\n",
    "            if target == 0:\n",
    "                return 0\n",
    "            if target < 0:\n",
    "                return float(inf)\n",
    "            if i < 0:\n",
    "                return float(inf)\n",
    "            res = min(dp(i-1, target), dp(i, target-coins[i])+1)\n",
    "            memo[name] = res\n",
    "            return res\n",
    "            \n",
    "        \n",
    "        res = dp(len(coins)-1, amount)\n",
    "\n",
    "        return -1 if res == float('inf') else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(i, target):\n",
    "            name = '{}_{}'.format(i, target)\n",
    "            if name in memo:\n",
    "                return memo[name]\n",
    "            if target == 0:\n",
    "                return 0\n",
    "            if target < 0:\n",
    "                return float('inf')\n",
    "            if i < 0:\n",
    "                return float('inf')\n",
    "            res = min(dp(i-1, target), dp(i, target-coins[i])+1)\n",
    "            memo[name] = res\n",
    "            return res\n",
    "            \n",
    "        \n",
    "        res = dp(len(coins)-1, amount)\n",
    "\n",
    "        return -1 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.coins=None\n",
    "    \n",
    "    @cache\n",
    "    def sub(self,amount):\n",
    "        if amount<0:\n",
    "            return -1\n",
    "        if amount==0:\n",
    "            return 0\n",
    "        \n",
    "        ret = -2\n",
    "        for i in self.coins:\n",
    "            sret = self.sub(amount-i)\n",
    "            if sret==-1:\n",
    "                pass\n",
    "            else:\n",
    "                if ret==-2:\n",
    "                    ret=sret\n",
    "                elif sret<ret:\n",
    "                    ret=sret\n",
    "        return ret+1\n",
    "\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.coins=coins\n",
    "        return self.sub(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.coins = coins\n",
    "        re = self.dp(amount)\n",
    "        if re==float('inf'):\n",
    "            return -1\n",
    "        return re\n",
    "        \n",
    "    @cache\n",
    "    def dp(self,number):\n",
    "        if number<0:\n",
    "            return float('inf')\n",
    "        if number==0:\n",
    "            return 0\n",
    "        re = float('inf')\n",
    "        for coin in self.coins:\n",
    "            re = min(self.dp(number-coin)+1,re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        def dp_memo(m):\n",
    "            if m == 0:\n",
    "                return 0\n",
    "            if m < 0: \n",
    "                return -1\n",
    "            if min_list[m] != -999:\n",
    "                return min_list[m]\n",
    "            res = 99999\n",
    "            for coin in coins:\n",
    "                coin_cnt = dp_memo(m - coin)\n",
    "                if coin_cnt == -1:\n",
    "                    continue\n",
    "                res = min(res, coin_cnt+1)\n",
    "            # print(\"set list %d for %d\" % (m, res))\n",
    "            min_list[m] = -1 if res == 99999 else res\n",
    "            return min_list[m]\n",
    "        min_list = [-999] * 200000\n",
    "        return dp_memo(amount)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.coins = sorted(coins, reverse=True)\n",
    "        res = self._change(amount)\n",
    "        return res if res != float(\"Inf\") else -1\n",
    "    @cache\n",
    "    def _change(self, left_amount):\n",
    "        if left_amount < 0:\n",
    "            return float(\"Inf\")\n",
    "        elif left_amount == 0:\n",
    "            return 0\n",
    "        \n",
    "        return min(self._change(left_amount - coin) for coin in self.coins) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    不同的面额，不重复\n",
    "    f(n) = 1 + f(n-v_coin)\n",
    "    \"\"\"\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.coins = coins\n",
    "        return self._coinChange(amount)\n",
    "\n",
    "    @lru_cache(maxsize=None)\n",
    "    def _coinChange(self, amount):\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "        coins = self.coins\n",
    "        if amount in coins:\n",
    "            return 1\n",
    "        if amount < min(coins):\n",
    "            return -1\n",
    "        n_coin = (self._coinChange(amount-coin) for coin in coins)\n",
    "        n_coin = [n for n in n_coin if n > 0]\n",
    "        if n_coin:\n",
    "            return min(n_coin) + 1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins, amount):\n",
    "        \"\"\"\n",
    "        :type coins: List[int]\n",
    "        :type amount: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [float('inf') for i in range(amount+1)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1,amount+1):\n",
    "            tp = float('inf')\n",
    "            for j in coins:\n",
    "                if j <= i:\n",
    "                    tp = min(tp,dp[i-j] + 1)\n",
    "            dp[i] = tp\n",
    "        return dp[amount] if dp[amount] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins = sorted(coins)[::-1]\n",
    "        _cahce = {}\n",
    "        def change(i, a):\n",
    "            if a == 0:\n",
    "                return 0\n",
    "            if (i, a) in _cahce:\n",
    "                return _cahce[(i, a)]\n",
    "            \n",
    "            counts = []\n",
    "            if a - coins[i] >= 0:\n",
    "                counts.append(change(i, a-coins[i]) + 1)\n",
    "            if i < len(coins) - 1:\n",
    "                counts.append(change(i+1, a))\n",
    "\n",
    "            res = min(counts) if len(counts) > 0 else amount + 1\n",
    "            _cahce[(i, a)] = res\n",
    "            return res\n",
    "        \n",
    "        res = change(0, amount)\n",
    "        return -1 if res > amount else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount < 0: return -1\n",
    "        if amount == 0: return 0\n",
    "        self.coins = coins\n",
    "        x = self.dp(amount)\n",
    "        if x == float(\"inf\"):\n",
    "            return -1\n",
    "        return x\n",
    "\n",
    "    @lru_cache(10000000)\n",
    "    def dp(self, aim):\n",
    "        if aim < 0: return float(\"inf\")\n",
    "        if aim == 0: return 0\n",
    "        res = float(\"inf\")\n",
    "        for i in self.coins:\n",
    "            res = min(res, 1 + self.dp(aim - i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount==0:return 0\n",
    "        coins.sort(reverse=True)\n",
    "        self.ans=float('inf')\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def f(cur,c):\n",
    "            if c>self.ans:return \n",
    "            if cur==amount:\n",
    "                self.ans=min(self.ans,c)\n",
    "            for i in coins:\n",
    "                if cur+i<=amount:\n",
    "                    f(cur+i,c+1)\n",
    "                \n",
    "        f(0,0)\n",
    "        return self.ans if self.ans!=float('inf') else -1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins = sorted(coins,reverse=True)\n",
    "        dic = {}\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "        @lru_cache(None)\n",
    "        def dfs(number,total):\n",
    "            if total > amount:\n",
    "                return float('inf')\n",
    "            if total == amount:\n",
    "                return number\n",
    "            res = float('inf')\n",
    "            if total not in dic:\n",
    "                dic[total] = number\n",
    "            else:\n",
    "                if dic[total] <= number:\n",
    "                    return res\n",
    "                dic[total] = number\n",
    "            for ele in coins:\n",
    "                res = min(dfs(number+1, ele+total),res)\n",
    "            return res\n",
    "        if dfs(0,0) == float('inf'):\n",
    "            return -1\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.ans=float(\"inf\")\n",
    "        coins.sort(reverse=1)\n",
    "        @lru_cache(None)\n",
    "        def case(num=0,amoun=amount):\n",
    "            if not amoun:\n",
    "\n",
    "                self.ans=min(self.ans,num)\n",
    "                return \n",
    "            if num>=self.ans:return \n",
    "            for i in coins:\n",
    "                if amoun-i>=0:\n",
    "                    case(num+1,amoun-i)\n",
    "            else:\n",
    "                return \n",
    "        case()\n",
    "        if self.ans==float(\"inf\"):\n",
    "            return -1\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        min_times= math.inf\n",
    "        times = 0\n",
    "        res = []\n",
    "        coins.sort(reverse = True)\n",
    "        @lru_cache(None)\n",
    "        def backtrace(target,times):\n",
    "            nonlocal min_times\n",
    "            if target < 0 or times > min_times:\n",
    "                return \n",
    "            elif target == 0:\n",
    "                res.append(times)\n",
    "                min_times = min(res)\n",
    "            else:\n",
    "                for c in coins:\n",
    "                    #print('target={},times={},c={}'.format(target,times,c))\n",
    "                    times += 1\n",
    "                    backtrace(target-c, times)\n",
    "                    times -= 1\n",
    "                    \n",
    "        backtrace(amount, times)\n",
    "        #print(res)\n",
    "        return -1 if len(res)==0 else min(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.dp = {}\n",
    "        self.ans = -1\n",
    "        coins.sort(reverse=True)\n",
    "        @cache\n",
    "        def back_track(amount,n):\n",
    "            if amount == 0:\n",
    "                if self.ans == -1:\n",
    "                    self.ans = n\n",
    "                elif self.ans > n:\n",
    "                    self.ans = n\n",
    "            if self.dp.get(amount) and self.dp.get(amount) <= n:\n",
    "                return\n",
    "            self.dp[amount] = n\n",
    "            for coin in coins:\n",
    "                if amount - coin >= 0:\n",
    "                    back_track(amount-coin,n+1)\n",
    "            \n",
    "        back_track(amount,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "        # dp = [amount+1]*(amount+1)\n",
    "        # for m in range(amount+1):\n",
    "        #     if not m % coins[0]:\n",
    "        #         dp[m] = m // coins[0]\n",
    "\n",
    "        # for i in range(1, len(coins)):\n",
    "        #     for m in range(coins[i], amount+1):\n",
    "        #         dp[m] = min(dp[m], dp[m-coins[i]]+1)\n",
    "        # return dp[amount] if dp[amount]<amount+1 else -1\n",
    "\n",
    "        dp = {}\n",
    "        def dfs(i, m):\n",
    "            if i == 0:\n",
    "                return m//coins[i] if not m%coins[i] else amount+1\n",
    "            if (i,m) in dp:\n",
    "                return dp[i,m]\n",
    "\n",
    "            cnt = dfs(i-1, m)\n",
    "            if coins[i] <= m:\n",
    "                cnt = min(cnt, 1 + dfs(i, m-coins[i]))\n",
    "            dp[i, m] = cnt\n",
    "            return dp[i, m]\n",
    "\n",
    "        cnt = dfs(len(coins)-1, amount)\n",
    "        return cnt if cnt<amount+1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, a: List[int], amount: int) -> int:\n",
    "        MAX = 999999\n",
    "        a.sort()\n",
    "        b = [a[0]]\n",
    "        for x in a[1:]:\n",
    "            b.append(gcd(x, b[-1]))\n",
    "        @cache\n",
    "        def f(x, k):\n",
    "            ans = MAX\n",
    "            if x % a[k] ==0:\n",
    "                return x//a[k]\n",
    "            elif x % b[k] !=0 or x < a[0]:\n",
    "                return MAX\n",
    "            return min(f(x-a[k], k)+1, f(x, k-1))\n",
    "        ans = f(amount, len(a)-1) \n",
    "        return -1 if ans == MAX else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins = sorted(coins, reverse=True)\n",
    "        @lru_cache(None)\n",
    "        def search(amount, n):\n",
    "            \n",
    "            if amount == 0: return 0\n",
    "            if n == len(coins):\n",
    "                return amount // coins[n] if n == len(coins) - 1 else -1\n",
    "            if n > 0 and amount > coins[n-1] * coins[n]: return -1\n",
    "            ans = -1\n",
    "            max_coins = amount // coins[n] if n == 0 else coins[n-1] - 1\n",
    "            # print(coins[n], max_coins , n)\n",
    "            max_coins =  min(amount//coins[n], max_coins)\n",
    "            # print(coins[n], max_coins , n)\n",
    "            for i in range(max_coins, -1, -1):\n",
    "                tmp = search(amount - i * coins[n], n+1)\n",
    "                # if final_ans[0] != -1 and tmp >= final_ans[0]: return -1\n",
    "                if tmp < 0: continue\n",
    "                if ans == -1 or tmp + i < ans:\n",
    "                    ans = tmp + i\n",
    "            return ans\n",
    "        return search(amount, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        def solve(i, n):\n",
    "            if i<0:\n",
    "                return float('inf')\n",
    "            if n==0:\n",
    "                return 0\n",
    "            key = '%d %d' % (i, n)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            elif coins[i]>n:\n",
    "                memo[key] = solve(i-1, n)\n",
    "            else:\n",
    "                A = solve(i, n-coins[i])+1\n",
    "                B = solve(i-1, n-coins[i])+1\n",
    "                C = solve(i-1, n)\n",
    "                memo[key] = min(A, B, C)\n",
    "            return memo[key]\n",
    "        memo = {}\n",
    "        res = solve(len(coins)-1, amount)\n",
    "        return res if res!=float('inf') else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 这和上一题一样, 这里是给价值求个数!\n",
    "        # 传统背包九讲里, 是求价值! 所以dp[i]的设计方式不一样, 意义也不一样\n",
    "        # lc = len(coins)\n",
    "        # dp = [float('inf')]*(amount+1)\n",
    "        # dp[0] = 0\n",
    "        # # coins_set = set(coins)\n",
    "        # for i in range(1, amount+1):\n",
    "        #     for j in range(lc):\n",
    "        #         if i>=coins[j]:\n",
    "        #             dp[i] = min(dp[i], dp[i-coins[j]]+1) \n",
    "        # return dp[-1] if dp[-1]!=float('inf') else -1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        if amount==0:\n",
    "            return 0\n",
    "        coins.sort()\n",
    "        ll = []\n",
    "        for item in coins:\n",
    "            if item>amount:\n",
    "                break\n",
    "            ll.append(item)\n",
    "        if not ll:\n",
    "            return -1\n",
    "        @cache\n",
    "        def run(goal, cur):\n",
    "            if goal==0:\n",
    "                return 0\n",
    "            if cur==0:\n",
    "                if goal%ll[cur]==0:\n",
    "                    return goal//ll[cur]\n",
    "                return inf\n",
    "            if goal-ll[cur]<0:\n",
    "                return run(goal, cur-1)\n",
    "            r = min(run(goal, cur-1), run(goal-ll[cur], cur)+1)\n",
    "            return r\n",
    "\n",
    "        t = run(amount, len(ll)-1)\n",
    "        return t if t<=10**4 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.coins = None\n",
    "    @cache\n",
    "    def helper(self, i, amount):\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "        if amount in self.coins[i:]:\n",
    "            return 1\n",
    "        if amount < self.coins[-1]:\n",
    "            return 1e16\n",
    "        \n",
    "        ans = 1e16\n",
    "        for j in range(len(self.coins)-i):\n",
    "            c = self.coins[j + i]\n",
    "            ans = min(ans, self.helper(i+j, amount-c) + 1)\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort(reverse = True)\n",
    "        self.coins = coins\n",
    "        ans = self.helper(0, amount)\n",
    "        return ans if ans < 1e16 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        coins.sort()\n",
    "        cache = {}\n",
    "        def loop(ind, target):\n",
    "\n",
    "            if target == 0:\n",
    "                return 0\n",
    "            \n",
    "            if (ind, target) not in cache:\n",
    "                current = ind\n",
    "                while current > -1 and coins[current] > target:\n",
    "                    current -= 1\n",
    "                \n",
    "                if current == -1:\n",
    "                    cache[(ind, target)] = float(\"inf\")\n",
    "\n",
    "                elif current == 0:\n",
    "                    if target % coins[0] == 0:\n",
    "                            cache[(ind, target)] = target // coins[0]\n",
    "                    else:\n",
    "                        cache[(ind, target)] = float(\"inf\")\n",
    "                else:\n",
    "                    cache[(ind, target)] = min(loop(current, target - coins[current]) + 1, loop(current -1, target))\n",
    "    \n",
    "            return cache[(ind, target)]\n",
    "\n",
    "        \n",
    "        res = loop(len(coins) - 1, amount)\n",
    "\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins = sorted(coins, reverse=True)\n",
    "\n",
    "        @cache\n",
    "        def helper(i, amount) -> int:\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "\n",
    "            if amount in coins[i:]:\n",
    "                return 1\n",
    "            \n",
    "            if amount < coins[-1]:\n",
    "                return 1e16\n",
    "\n",
    "            ans = 1e16\n",
    "            if amount >= coins[-1]:            \n",
    "                for j in range(i, len(coins)):\n",
    "                    if amount - coins[j] > 0:\n",
    "                        ans = min(ans, 1 + helper(j, amount - coins[j]))\n",
    "\n",
    "            return ans\n",
    "            \n",
    "        ans = helper(0, amount)\n",
    "        return ans if ans < 1e16 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        coins.sort()\n",
    "        cache = {}\n",
    "        def loop(ind, target):\n",
    "\n",
    "            if target == 0:\n",
    "                return 0\n",
    "            \n",
    "            if (ind, target) not in cache:\n",
    "                current = ind\n",
    "                while current > -1 and coins[current] > target:\n",
    "                    current -= 1\n",
    "                \n",
    "                if current == -1:\n",
    "                    cache[(ind, target)] = float(\"inf\")\n",
    "\n",
    "                elif current == 0:\n",
    "                    if target % coins[0] == 0:\n",
    "                            cache[(ind, target)] = target // coins[0]\n",
    "                    else:\n",
    "                        cache[(ind, target)] = float(\"inf\")\n",
    "                else:\n",
    "                    cache[(ind, target)] = min(loop(ind, target - coins[ind]) + 1, loop(ind -1, target))\n",
    "    \n",
    "            return cache[(ind, target)]\n",
    "\n",
    "        \n",
    "        res = loop(len(coins) - 1, amount)\n",
    "    \n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        \"\"\" 回溯枚举 \"\"\"\n",
    "        coins.sort(reverse=True)\n",
    "        n = len(coins)\n",
    "        INF = float('inf')\n",
    "        @cache\n",
    "        def dfs(i, s):\n",
    "            \"\"\" 回溯遍历, i 表示序列索引开头, s是剩下的和, cnt是硬币个数 \"\"\"\n",
    "            # print(i, s, cnt)\n",
    "            if s <= 0:\n",
    "                if s == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return INF\n",
    "            \n",
    "            Min = INF\n",
    "            for j in range(i, n):\n",
    "                # 如果当前硬币太大, 尝试往后找更小的\n",
    "                if coins[j] > s:\n",
    "                    continue\n",
    "                \n",
    "                ret = dfs(j, s - coins[j]) + 1\n",
    "                Min = min(Min, ret)\n",
    "                # # 如果成功找到解, 返回\n",
    "                # if ret != -1:\n",
    "                #     return ret\n",
    "            \n",
    "            return Min\n",
    "        \n",
    "        ans = dfs(0, amount)\n",
    "        return ans if ans != INF else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort(reverse=True)\n",
    "        @cache\n",
    "        def f(amount, idx):            \n",
    "            if amount == 0:\n",
    "                return 0            \n",
    "            ans = float(\"inf\")\n",
    "            for i in range(idx, len(coins)):\n",
    "                if amount >= coins[i]:\n",
    "                    ans = min(ans, f(amount - coins[i], i) + 1)\n",
    "            return ans\n",
    "        ans = f(amount, 0)\n",
    "        return ans if ans != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo=dict()\n",
    "        def dp(i,t):\n",
    "            if t==0:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                if t%coins[i]==0:\n",
    "                    return t//coins[i]\n",
    "                else:\n",
    "                    return float('Inf')\n",
    "            if (i,t) in memo:\n",
    "                return memo[(i,t)]\n",
    "            a=dp(i-1,t)\n",
    "            b=dp(i,t-coins[i])+1 if t-coins[i]>=0 else float('Inf')\n",
    "            memo[(i,t)] = min(a,b)\n",
    "            return memo[(i,t)]\n",
    "        res=dp(len(coins)-1,amount)\n",
    "        return res if res!=float('Inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        \n",
    "        if amount == 0:\n",
    "            return 0\n",
    "\n",
    "        coins = sorted(coins, reverse=True)\n",
    "\n",
    "        cache = {}\n",
    "\n",
    "        def loop(ind, rest):\n",
    "            \n",
    "            if ind == len(coins):\n",
    "                return float('inf')\n",
    "            \n",
    "            if coins[ind] == rest:\n",
    "                return 1\n",
    "\n",
    "            if (ind, rest) not in cache:\n",
    "                if rest > coins[ind]:\n",
    "                    cache[(ind, rest)] = min(loop(ind, rest - coins[ind]) + 1, loop(ind + 1, rest))\n",
    "                else:\n",
    "                    cache[(ind, rest)] = loop(ind + 1, rest)\n",
    "            \n",
    "            return cache[(ind, rest)]\n",
    "        \n",
    "        ans = loop(0, amount)\n",
    "\n",
    "        if ans < float('inf'):\n",
    "            return ans\n",
    "\n",
    "        return -1\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从前往后/从下往上的递推，也即动态规划\n",
    "    '''\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        #index是金额，value是硬币数量.\n",
    "        # dp=[float('inf')]*(amount+1)#注意，如果是别的语言可能会存在溢出的问题\n",
    "        dp=[amount+1]*(amount+1)#不用担心溢出问题\n",
    "        combs=[[]]*(amount+1)\n",
    "        dp[0]=0\n",
    "        if amount==0:\n",
    "            return 0\n",
    "        for i in range(1,len(dp)):#遍历每种金额\n",
    "            for coin in coins: #遍历每种硬币\n",
    "                if i-coin<0:\n",
    "                    continue\n",
    "                if dp[i-coin]+1<dp[i]:\n",
    "                    dp[i]=dp[i-coin]+1\n",
    "                    combs[i]=combs[i-coin]+[coin]\n",
    "        # if dp[-1]==float('inf'):\n",
    "        if dp[-1]>=amount+1:\n",
    "            res=-1\n",
    "        else:\n",
    "            res=dp[-1]\n",
    "        # print(combs[-1])\n",
    "        if combs[-1]==[]:\n",
    "            res=-1\n",
    "        else:\n",
    "            res=len(combs[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    带备忘录的递归，增加详细结果\n",
    "    '''\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount<0:\n",
    "            return -1\n",
    "        if amount==0:\n",
    "            return 0\n",
    "        self.memo_list=[float('inf')]*(amount+1)\n",
    "        self.memo_list[0]=0\n",
    "        self.combos = [[]] *(amount + 1)  # 新增数组来存储硬币组合\n",
    "\n",
    "        def recursion(coins: List[int], amount: int):\n",
    "            if amount<0:\n",
    "                return -1\n",
    "            if amount==0:\n",
    "                return 0\n",
    "            if self.memo_list[amount]!=float('inf'):\n",
    "                return self.memo_list[amount]\n",
    "            res=float('inf')#正无穷\n",
    "            for coin in coins:\n",
    "                sub_porblem=recursion(coins,amount-coin)\n",
    "                if amount-coin>=0:\n",
    "                    self.memo_list[amount-coin]=sub_porblem\n",
    "                if sub_porblem==-1:#说明当前coin不是可行解，跳过\n",
    "                    continue\n",
    "                if sub_porblem+1<res:#说明当前coin是个局部最优解，继续和下一个coin的结果对比\n",
    "                    res=sub_porblem+1\n",
    "                    self.memo_list[amount]=res\n",
    "                    self.combos[amount] = self.combos[amount - coin] + [coin]  # 记录硬币组合\n",
    "                else:#说明当前coin不是个局部最优解，继续从下一个coin找局部最优解\n",
    "                    continue\n",
    "\n",
    "            if res==float('inf'):#当前层的更下层的遍历结果没有找到可行的解\n",
    "                res=-1#提示上一层递归，本次没找到解\n",
    "            return res\n",
    "        res=recursion(coins, amount)\n",
    "        # print(self.memo_list)\n",
    "        # print(self.combos[-1])\n",
    "        final_res=-1\n",
    "        if self.combos[-1]!=[]:\n",
    "            final_res=len(self.combos[-1])\n",
    "        return final_res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
